/*
#include<stdio.h>
#include<iostream>
struct treenode {
	treenode* left;
	treenode* right;
	int data;

};

treenode* create() {
	int k;
	scanf("%d", &k);
	if (k == 0) return NULL;
	treenode* root = new treenode;
	root->data = k;
	root->left = create();
	root->right = create();
	return root;
}

typedef struct treenode TN;
void visit(int data) {
	printf("%d ", data);
}
void inorder(TN* root) {
	if (root == NULL) return;
	inorder(root->left);
	visit(root->data);
	inorder(root->right);
}

void del(treenode*& root) {
	if (root == NULL) return;
	del(root->left);
	del(root->right);
	delete root;
	root = NULL;
}

bool delt(treenode*& root, treenode* p) {
	if (root == NULL || p == NULL) return false;
	if (p == root) { del(root); return true; }
	if (delt(root->left, p)) return true;
	return delt(root->right, p);
}

treenode* search(treenode* root, int k) {
	if (root == NULL) return NULL;
	if (root->data == k) return root;
	treenode* ans = search(root->left, k);
	if (ans != NULL) return ans;
	return search(root->right, k);
}

int main() {
	int m, k[110];
	treenode* rot = create();
	scanf("%d", &m);
	int p;
	for (p = 0; p < m; p++) {
		scanf("%d", &k[p]);
	}
	for (p = 0; p < m; p++) {
		struct treenode* v = search(rot, k[p]);
		if (v == NULL) { printf("0\n"); continue; }
		delt(rot, v);
		inorder(rot);
		printf("\n");

	}
	return 0;
}
*/



#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct treenode {
	int data;
	treenode* left;
	treenode* right;
};

struct val {
	char hou[30];
	char zho[30];
};
treenode* root;

void preorder(treenode* root) {
	if (root == NULL) return;
	printf("%d", root->data);
	preorder(root->left);
	preorder(root->right);
}

void inorder(treenode* root) {
	if (root = NULL) return;
	inorder(root->left);
	printf("%d", root->data);
	inorder(root->right);
}

void postorder(treenode* root) {
	if (root = NULL) return;
	inorder(root->left);
	inorder(root->right);
	printf("%d", root->data);
}
int depth(treenode* root) {
	if (root == NULL) return -1;
	int d1 = depth(root->left);
	int d2 = depth(root->right);
	return(d1 > d2) ? d1 + 1 : d2 + 1;
}

int findroot(char* zho, int size, char val) {
	for (int i = 0; i < size; i++)
		if (zho[i] == val) return i;
	return -1;
}
treenode* build(char* hou, char* zho, int n) {
	if (n <= 0)return NULL;
	root = (treenode*)malloc(sizeof(treenode));
	if (hou[0] == zho[0]) root->data = zho[1];
	else if (hou[1] == zho[0]) root->data = zho[1];
	else { printf("INVALID\n"); return NULL; }
	int k = findroot(zho, n, root->data);
	root->left = build(&hou[0], &zho[1], k);
	root->right = build(&hou[k], &zho[k + 1], n - k);
	return root;

}
struct val value[10];
int mian() {
	int m = -1;
	do {
		m++;
		scanf("%s", &value[m].hou);
		scanf("%s", &value[m].zho);
	} while (value[m].hou != NULL);
	int n = m + 1;
	int a;
	for (a = 0; a <= m; a++) {
		build(value[a].hou, value[a].zho, n);
		if (root == NULL) continue;
		else {
			printf("%d\n", depth(root));
			preorder(root);
			printf("\n");
		};
	}
	return 0;
}